package com.leetCode.problem;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-07 14:08:03
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-07     张李鑫                     1.0         1.0 Version
 */
public class Problem37 {
    /**
     * 编写一个程序，通过填充空格来解决数独问题。
     * <p>
     * 数独的解法需 遵循如下规则：
     * <p>
     * 数字1-9在每一行只能出现一次。
     * 数字1-9在每一列只能出现一次。
     * 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
     * 数独部分空格内已填入了数字，空白格用'.'表示。
     */
//    public static boolean[][] rowArr = new boolean[8][10];
//    public static boolean[][] colArr = new boolean[8][10];
//    public static boolean[][] Arr = new boolean[8][10];

    public static boolean initMap(char[][] arr, boolean[][] rowArr, boolean[][] colArr, boolean[][] Arr) {
        for (int i = 0; i < 9; i++) {
            for (int i1 = 0; i1 < 9; i1++) {
                if (arr[i][i1] != '.') {
                    int bid = 3 * (i / 3) + (i1 / 3);
                    int val = arr[i][i1]-'0';
                    if (rowArr[i][val] || colArr[i1][val] || Arr[bid][val]) {
                        return false;
                    }
                    rowArr[i][val] = true;
                    colArr[i1][val] = true;
                    Arr[bid][val] = true;
                }
            }
        }
        return true;
    }

    public void solveSudoku(char[][] board) {
        boolean[][] rowArr = new boolean[9][10];
        boolean[][] colArr = new boolean[9][10];
        boolean[][] Arr = new boolean[9][10];
        initMap(board,rowArr,colArr,Arr);
        process(board, 0, 0,rowArr,colArr,Arr);
    }

    public static boolean process(char[][] board, int i, int j, boolean[][] rowArr, boolean[][] colArr, boolean[][] Arr) {
        if (i == 9) {
            return true;
        }
        int nextI = j == 8 ? i + 1 : i;
        int nextJ = j == 8 ? 0 : j + 1;
        if (board[i][j] != '.') {
            return process(board, nextI, nextJ, rowArr, colArr, Arr);
        } else {
            int bid = 3 * (i / 3) + (j / 3);
            for (int k = 1; k < 10; k++) {
                if (!Arr[bid][k] && !rowArr[i][k] && !colArr[j][k]) {
                    rowArr[i][k] = true;
                    colArr[j][k] = true;
                    Arr[bid][k] = true;
                    board[i][j] = (char) (k + '0');
                    if (process(board, nextI, nextJ, rowArr, colArr, Arr)) {
                        return true;
                    }
                    rowArr[i][k] = false;
                    colArr[j][k] = false;
                    Arr[bid][k] = false;
                    board[i][j] = '.';
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {

    }
}